/**
给定两个字符串A和B，长度分别为m和n，设计动态规划算法找出它们最长公共子序列长度，并给出最长公共子序列。例如：A = "HelloWorld"，B = "loopbird"，则A与B的最长公共子序列为"loord"，返回的长度为5。
*/
#include <stdio.h>

int init(int OPT[20][20])
{
	int i = 0, j = 0;

	for (i = 0; i < 20; i++) {
		for (j = 0; j < 20; j++) {
			OPT[i][j] = -1;
		}
	}
}

int find(char *A, int m, char c)
{
	int res = 0;
	
	for (res = m; res >= 0; res--) {
		if (A[res] == c) {
			printf("find %c in %d\n", c, res);
			break;
		}
	}

	return res;
}

int func(char *A, int m, char *B, int n, int OPT[20][20])
{
	int a = 0, b = 0, k = 0;
	if (m < 0 || n < 0) {
		return 0;
	}

	if (OPT[m][n] != -1) {
		printf("have set value: OPT[%d][%d] = %d\n", m, n, OPT[m][n]);
		return OPT[m][n];
	}

	k = find(A, m, B[n]);
	if (k >= 0) {
		a = func(A, m, B, n - 1, OPT);
		b = func(A, k - 1, B, n - 1, OPT) + 1;
		
		if (b > a) {
			OPT[m][n] = b;
		}
		else {
			OPT[m][n] = a;
		}
	}
	else {
		OPT[m][n] = func(A, m, B, n - 1, OPT);
	}

	printf("OPT[%d][%d] = %d\n", m, n, OPT[m][n]);
	return OPT[m][n];
}

void main()
{
	char A1[] = "HelloWorld";
	int m1 = 10;
	char B1[] = "loopbird";
	int n1 = 8;

	char A2[] = "12312345";
	int m2 = 8;
	char B2[] = "12345";
	int n2 = 5;


	int OPT[20][20] = { 0 };


	init(OPT);
	printf("A1 = %s   B1 = %s  maxSub = %d\n", A1, B1, func(A1, m1 - 1, B1, n1 - 1, OPT));


	printf("-----------------------------------------------------\n");
	init(OPT);
	printf("A2 = %s   B2 = %s  maxSub = %d\n", A2, B2, func(A2, m2 - 1, B2, n2 - 1, OPT));



	getchar();
}